package datastructure.sort;

import datastructure.sort.Insert;

import java.util.Arrays;

/**
 * @author or2
 * @date 2021/7/16 17:14
 */
public class Merger {
    /**
     * 归并排序算法
     * @param arr 需要排序的数组
     * @param <E> 实现了Comparable类型的泛型接口
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length-1);
    }

    /**
     * 递归调用 归并排序
     * @param arr 需要排序的数组
     * @param start 开始位置
     * @param end 终止位置
     * @param <E> 实现了Comparable类型的泛型接口
     */
    private static <E extends Comparable<E>> void sort(E[] arr, int start, int end) {
        /*递归终止条件 下面是优化
        if (start >= end) return;*/
//        数组规模过小时, 归并排序效率低 → 替换为插入排序
        if (end - start < 16) {
            Insert.sort(arr, start, end);
            return;
        }

        //防止 整型+ 越界; 使用位运算加快
        int mid =start + (end - start >> 1);
        sort(arr, start, mid);
        sort(arr, mid+1, end);

//        有序时不合并, 在数组整体有序时 → 时间复杂度为O(n)
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, start, mid, end);
        }
    }

    public static <E extends Comparable<E>> void sortBU(E[] arr) {
        int length = arr.length;
        E[] aidArr = arr.clone();

//        逐步扩大合并区间, i: 区间长度
        for (int i = 1; i < length; i += i) {
//            在每个区间内进行合并
//            合并 {@code [j, j + i - 1], [j + i, Math.min(length - 1, j + i + i - 1)]}
            for (int j = 0; j < length - i; j += i + i) {
//                优化 :→ 有序不合并
                if (arr[j + i - 1].compareTo(arr[j + i]) > 0) {
                    mergeOptimize(arr, j, j + i - 1, Math.min(length - 1, j + i + i - 1), aidArr);
                }
            }
        }

    }

    /**
     * 合并两个有序的数组区间 {@code arr[startIndex, midIndex], arr[midIndex+1, endIndex] }
     * @param arr 合并的数组
     * @param startIndex 合并开始的数组下标
     * @param midIndex 合并的中间边界
     * @param endIndex 合并的结束位置下标
     * @param <E> 实现了Comparable类型的泛型接口
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int startIndex, int midIndex, int endIndex) {
//        数组复制函数的操作数区间 [)
        E[] auxArr = Arrays.copyOfRange(arr, startIndex, endIndex + 1);
//        l: 数组一起始指针; h: 数组二起始指针
        int l = startIndex, h = midIndex + 1;
        for (int k = startIndex; k <= endIndex; k++) {
//            若数组一遍历结束, 后面将只取数组二的元素
            if (l > midIndex) {
                arr[k] = auxArr[h - startIndex];
                h++;
                continue;
            }
            if (h > endIndex) {
                arr[k] = auxArr[l - startIndex];
                l++;
                continue;
            }
//            若数组一小, 从一中取; 否则从二中取
            if (auxArr[l - startIndex].compareTo(auxArr[h - startIndex]) < 0) {
                arr[k] = auxArr[l - startIndex];
                l++;
            } else {
                arr[k] = auxArr[h - startIndex];
                h++;
            }

        }
    }

    /**
     * 优化内存使用的 ‘归并排序’
     * @deprecated 看不到任何优化？为什么？
     */
    @Deprecated
    public static <E extends Comparable<E>> void sortOptimize(E[] arr) {
        E[] aidArr = arr.clone();
        sortOptimize(arr, 0, arr.length-1, aidArr);
    }

    /**
     * 递归调用 归并排序
     * @param arr 需要排序的数组
     * @param start 开始位置
     * @param end 终止位置
     * @param <E> 实现了Comparable类型的泛型接口
     */
    private static <E extends Comparable<E>> void sortOptimize (E[] arr, int start, int end, E[] aidArr) {
        /*递归终止条件 下面是优化
        if (start >= end) return;*/
//        数组规模过小时, 归并排序效率低 → 替换为插入排序
        if (end - start < 16) {
            Insert.sort(arr, start, end);
            return;
        }

        //防止 整型+ 越界; 使用位运算加快
        int mid =start + (end - start >> 1);
        sortOptimize(arr, start, mid, aidArr);
        sortOptimize(arr, mid+1, end, aidArr);

//        有序时不合并, 在数组整体有序时 → 时间复杂度为O(n)
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            mergeOptimize(arr, start, mid, end, aidArr);
        }
    }

    /**
     * 合并两个有序的数组区间 {@code arr[startIndex, midIndex], arr[midIndex+1, endIndex] }
     * @param arr 合并的数组
     * @param startIndex 合并开始的数组下标
     * @param midIndex 合并的中间边界
     * @param endIndex 合并的结束位置下标
     * @param <E> 实现了Comparable类型的泛型接口
     */
    private static <E extends Comparable<E>> void mergeOptimize(E[] arr, int startIndex, int midIndex, int endIndex, E[] aidArr) {
//        数组复制函数的操作数区间 [)
        System.arraycopy(arr, startIndex, aidArr, startIndex, endIndex - startIndex + 1);
//        l: 数组一起始指针; h: 数组二起始指针
        int l = startIndex, h = midIndex + 1;
        for (int k = startIndex; k <= endIndex; k++) {
//            若数组一遍历结束, 后面将只取数组二的元素
            if (l > midIndex) {
                arr[k] = aidArr[h];
                h++;
                continue;
            }
            if (h > endIndex) {
                arr[k] = aidArr[l];
                l++;
                continue;
            }
//            若数组一小, 从一中取; 否则从二中取
            if (aidArr[l].compareTo(aidArr[h]) < 0) {
                arr[k] = aidArr[l];
                l++;
            } else {
                arr[k] = aidArr[h];
                h++;
            }

        }
    }
}
